#include "main/utils.h"
using namespace std;

bool isMapAllZero(const map<char, int> &help_map) {
  for (auto ele : help_map) {
    if (ele.second != 0) {
      return false;
    }
  }
  return true;
}

vector<int> isAnagram(const string &s1, const string &s2) {
  vector<int> ret;
  if (s1.length() < s2.length()) {
    return ret;
  }
  map<char, int> help_map;
  for (int i = 0; i < s2.size(); ++i) {
    if (help_map.find(s2[i]) == help_map.end()) {
      help_map[s2[i]] = 1;
    } else {
      ++help_map[s2[i]];
    }
    if (help_map.find(s1[i]) == help_map.end()) {
      help_map[s1[i]] = -1;
    } else {
      --help_map[s1[i]];
    }
  }

  int begin = 0;
  int end = s2.size() - 1;
  while (end < s1.size()) {
    if (isMapAllZero(help_map)) {
      ret.push_back(begin);
    }
    if (help_map.find(s1[++end]) == help_map.end()) {
      help_map[s1[end]] = -1;
    } else {
      --help_map[s1[end]];
    }
    ++help_map[s1[begin++]];
  }
  return ret;
}

int main() {
  string s1 = "cbadabacg";
  string s2 = "abc";
  auto ret = isAnagram(s1, s2);
  printVec("anagram index", ret);

  s1 = "aghoege";
  s2 = "abc";
  ret = isAnagram(s1, s2);
  printVec("anagram index", ret);

  s1 = "aghoegeaaa";
  s2 = "a";
  ret = isAnagram(s1, s2);
  printVec("anagram index", ret);

  return 0;
}
